/**
 * 1
 *  
 * @Author : roryrywang
 * @DateTime : 24-8-25 下午2:39
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        int n;
        scanf("%d", &n);

        vector<int> v(n);
        for (int j = 0; j < n; ++j) {
            scanf("%d", &v[j]);
        }

        int a, b, c, sum = 0;
        vector<int> w;
        for (int j = 0; j < n - 1; ++j) {
            scanf("%d %d %d", &a, &b, &c);
            w.push_back(c);
            sum += c;
        }
        sort(w.begin(), w.end());

        int res = v[0] + sum;
        for (int j = 0; j < n - 1; ++j) {
            sum -= w[j];
            res = max(res, v[j + 1] + sum);
        }

        cout << res << endl;
    }
    return 0;
}